import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

public class Solution {
    public int[] dailyTemperatures(int[] T) {
        Stack<Integer> stack = new Stack<>();
        int len = T.length;
        int[] res = new int[len];
        for (int i = 0; i < len; i++) {

            for (Integer integer : stack) {  // 注意这里的代码直接用foreach
                res[integer]++;
            }
            while (!stack.isEmpty() && T[stack.peek()] < T[i]) {
                stack.pop();

            }
            stack.push(i);
        }
        for (Integer integer : stack) {
            res[integer] = 0;
        }
        return res;
    }

    /*上面的方法超时*/
    public int[] dailyTemperatures2(int[] T) {
        // Stack<Integer> stack = new Stack<>();
        Deque<Integer> stack = new LinkedList<>(); // 效率更高
        /*这里总结一下deque
        1.当stack使用用：push，pop，peek
        2.queue使用：offer，poll，peek（element）

        * */
        int len = T.length;
        int[] res = new int[len];
        for (int i = 0; i < len; i++) {


            while (!stack.isEmpty() && T[stack.peek()] < T[i]) {
                int temp = stack.pop();
                res[temp] = i - temp;

            }
            stack.push(i);
        }

        return res;

    }
}
